#ifndef BT_H_
#define BT_H_

#include <algorithm>
#include <climits>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <vector>

// 实现细节，外界不能调用
namespace
{
template<class T, std::enable_if_t<std::is_arithmetic_v<T>, int> = 0>
struct Node {
    T     _value;
    Node* left;
    Node* right;
};

inline Node<int>* build_detail(std::vector<int>&                preorder,
                               int                              a,
                               int                              b,
                               std::vector<int>&                inorder,
                               int                              i,
                               int                              j,
                               std::unordered_map<int, size_t>& m)
{
    if (a > b) return nullptr;

    Node<int>* head = new Node<int>{._value = preorder[a], .left = nullptr, .right = nullptr};
    if (a == b) return head;

    int k       = m[preorder[a]];
    head->left  = build_detail(preorder, a + 1, a + k - i, inorder, i, k - 1, m);
    head->right = build_detail(preorder, a + k - i + 1, b, inorder, k + 1, j, m);
    return head;
}

template<class T>
inline int most_left(Node<T>* cur, int level)
{
    while (cur != nullptr) {
        level++;
        cur = cur->left;
    }
    return level - 1;
}

template<class T>
inline int f(Node<T>* cur, int level, int h)
{
    if (level == h) return 1;
    if (most_left(cur->right, level + 1) == h) {
        return ((1 << (h - level)) + f(cur->right, level + 1, h));
    }
    else {
        return ((1 << (h - level - 1)) + f(cur->left, level + 1, h));
    }
}

template<class T>
inline int height(Node<T>* root, bool& balance)
{
    if (!balance || root == nullptr) return 0;
    int lh = height(root->left, balance);
    int rh = height(root->right, balance);
    if (std::abs(lh - rh) >= 2) balance = false;

    return std::max(lh, rh) + 1;
}

template<class T>
inline int BST(Node<T>* root)
{
    return 0;
}

template<class T>
inline void rob(Node<T>* root, T& yes, T& no)
{
    if (root == nullptr) {
        yes = 0;
        no  = 0;
    }
    else {
        T y = root->_value;
        T n = 0;
        rob(root->left, yes, no);
        y += no;
        n += yes > no ? yes : no;
        rob(root->right, yes, no);
        y += no;
        n += yes > no ? yes : no;
        yes = y;
        no  = n;
    }
}

}   // namespace

namespace lxj
{

template<class T, std::enable_if_t<std::is_arithmetic_v<T>, int> = 0>
class BinaryTree {
    Node<T>* _head;
    size_t   _size;

public:
    BinaryTree(Node<T>* head) : _head(head) {}

    template<typename Iter>
    BinaryTree(Iter first, Iter last)
    {
        std::_Adl_verify_range(first, last);

        auto       ufirst = std::_Get_unwrapped(first);
        const auto ulast  = std::_Get_unwrapped(last);
        using type        = std::remove_cv_t<std::remove_pointer_t<decltype(ufirst)>>;
        static_assert(std::is_same_v<T, type>, "模板类型参数不匹配");

        _head = new Node<T>{._value = *(ufirst), .left = nullptr, .right = nullptr};
        ufirst++;
        _size                    = ulast - ufirst;
        decltype(_head)      cur = nullptr;
        std::queue<Node<T>*> node_que;
        node_que.push(_head);
        while (!node_que.empty()) {
            cur = node_que.front();
            node_que.pop();
            if (ulast - ufirst > 0) {
                cur->left = new Node<T>{._value = *(ufirst++), .left = nullptr, .right = nullptr};
                node_que.push(cur->left);
            }
            if (ulast - ufirst > 0) {
                cur->right = new Node<T>{._value = *(ufirst++), .left = nullptr, .right = nullptr};
                node_que.push(cur->right);
            }
        }
        while (!node_que.empty()) {
            node_que.pop();
        }
    }

    BinaryTree(const BinaryTree&) = delete;

    BinaryTree(BinaryTree&& other) : _head(other._head), _size(other._size)
    {
        other._head = nullptr;
    }

    ~BinaryTree()
    {
        std::queue<Node<T>*> node;
        node.push(_head);
        Node<T>* cur = nullptr;
        while (!node.empty()) {
            cur = node.front();
            node.pop();
            cur->left == nullptr ? (void)0 : node.push(cur->left);
            cur->right == nullptr ? (void)0 : node.push(cur->right);
            delete cur;
        }
    }

public:
    Node<T>* get_head() { return _head; }
    // 层序遍历
    inline void level_print() const
    {
        if (_head == nullptr) return;

        std::queue<Node<T>*> node_que;
        node_que.push(_head);
        Node<T>* cur = nullptr;
        while (!node_que.empty()) {
            cur = node_que.front();
            node_que.pop();
            auto value = cur->_value;
            std::cout << value << ", ";
            cur->left == nullptr ? (void)0 : node_que.push(cur->left);
            cur->right == nullptr ? (void)0 : node_que.push(cur->right);
        }
        std::puts("");
    }

    // 力扣103. 二叉树的锯齿形层序遍历
    inline std::vector<std::vector<T>> zigzagLevelOrder()
    {
        if (_head == nullptr) return std::vector<std::vector<T>>{};

        std::vector<std::vector<T>> vvi;
        int                         direction = 1;
        std::queue<Node<T>*>        que;
        que.push(_head);

        while (!que.empty()) {
            int            size = que.size();
            std::vector<T> vi(size);
            int            index = direction == 1 ? 0 : size - 1;
            while (size--) {
                Node<T>* cur = que.front();
                que.pop();
                cur->left != nullptr ? que.push(cur->left) : (void)0;
                cur->right != nullptr ? que.push(cur->right) : (void)0;
                vi[index] = cur->_value;
                index += direction;
            }
            direction *= -1;
            vvi.push_back(vi);
        }
        return vvi;
    }
};

// 释放二叉树
template<class T>
inline void delete_tree(Node<T>* head)
{
    std::queue<Node<T>*> node;
    node.push(head);
    Node<T>* cur = nullptr;
    while (!node.empty()) {
        cur = node.front();
        node.pop();
        cur->left == nullptr ? (void)0 : node.push(cur->left);
        cur->right == nullptr ? (void)0 : node.push(cur->right);
        delete cur;
    }
}

// 力扣662. 二叉树的最大特殊宽度
template<class T>
inline int widthOfBinaryTree(Node<T>* head)
{
    if (head == nullptr) return 0;

    int      ans      = 1;
    Node<T>* nq[3001] = {};
    int      iq[3001] = {};
    int      l = 0, r = 0;
    nq[r]   = head;
    iq[r++] = 1;
    while (l < r) {
        int size = r - l;
        ans      = ans > iq[r - 1] - iq[l] + 1 ? ans : iq[r - 1] - iq[l] + 1;
        for (int i = 0; i < size; i++) {
            Node<T>*           node = nq[l];
            unsigned long long id   = iq[l++];
            if (node->left != nullptr) {
                nq[r]   = node->left;
                iq[r++] = id * 2ul;
            }
            if (node->right != nullptr) {
                nq[r]   = node->right;
                iq[r++] = id * 2 + 1;
            }
        }
    }

    return ans;
}

// 力扣104. 二叉树的最大深度
template<class T>
inline int maxDepth(Node<T>* root)
{
    return root == nullptr ? 0 : std::max(maxDepth(root->left), maxDepth(root->right)) + 1;
}

// 力扣111. 二叉树的最小深度
template<class T>
inline int minDepth(Node<T>* root)
{
    if (root == nullptr) return 0;
    if (root->left == nullptr && root->right == nullptr) return 1;

    int ldeep = INT_MAX;
    int rdeep = INT_MAX;
    if (root->left != nullptr) {
        ldeep = minDepth(root->left);
    }
    if (root->right != nullptr) {
        rdeep = minDepth(root->right);
    }
    return std::min(ldeep, rdeep) + 1;
}

// 297. 二叉树的序列化与反序列化
class Codec {
public:
    // Encodes a tree to a single string.(先序递归版)
    inline std::string serialize(Node<int>* root)
    {
        std::string str;
        serialize(root, str);
        return str;
    }

    inline void serialize(Node<int>* root, std::string& s)
    {
        if (root == nullptr) {
            s += "#,";
        }
        else {
            s = s + std::to_string(root->_value) + ",";
            serialize(root->left, s);
            serialize(root->right, s);
        }
    }

    // 层序版
    inline std::string level_serialize(Node<int>* root)
    {
        if (root == nullptr) return "";
        std::string            result;
        std::queue<Node<int>*> que;
        result += std::to_string(root->_value) + ',';
        que.push(root);
        while (!que.empty()) {
            Node<int>* cur = que.front();
            que.pop();
            if (cur->left != nullptr) {
                result += std::to_string(cur->left->_value) + ',';
                que.push(cur->left);
            }
            else {
                result += "#,";
            }
            if (cur->right != nullptr) {
                result += std::to_string(cur->right->_value) + ',';
                que.push(cur->right);
            }
            else {
                result += "#,";
            }
        }
        return result;
    }

    // Decodes your encoded data to tree.(先序递归版)
    inline Node<int>* deserialize(std::string data)
    {
        data += ',';
        std::vector<std::string> vs;
        for (int i = 0; i < data.size(); i++) {
            std::string s;
            while (data[i] != ',') {
                s += data[i++];
            }
            s.empty() ? (void)0 : vs.push_back(s);
        }

        int index = 0;
        return deserialize(vs, index);
    }

    inline Node<int>* deserialize(std::vector<std::string>& vec, int& index)
    {
        std::string s = index >= vec.size() ? "#" : vec[index++];
        if (s == "#") return nullptr;
        Node<int>* head = new Node<int>{._value = std::stoi(s), .left = nullptr, .right = nullptr};
        head->left      = deserialize(vec, index);
        head->right     = deserialize(vec, index);
        return head;
    }

    // 层序版
    inline Node<int>* level_deserialize(std::string data)
    {
        if (data.empty()) return nullptr;
        data += ',';
        std::vector<std::string> vs;
        for (int i = 0; i < data.size(); i++) {
            std::string s;
            while (data[i] != ',') {
                s += data[i++];
            }
            s.empty() ? (void)0 : vs.push_back(s);
        }

        auto generate = [&vs](size_t index) -> Node<int>* {
            if (index >= vs.size() || vs[index] == "#") return nullptr;
            return new Node<int>{._value = std::stoi(vs[index]), .left = nullptr, .right = nullptr};
        };

        std::queue<Node<int>*> que;
        int                    index = 0;
        Node<int>*             head  = generate(index++);
        que.push(head);
        while (!que.empty()) {
            Node<int>* cur = que.front();
            que.pop();
            cur->left  = generate(index++);
            cur->right = generate(index++);
            cur->left != nullptr ? que.push(cur->left) : (void)0;
            cur->right != nullptr ? que.push(cur->right) : (void)0;
        }
        return head;
    }
};

// 力扣105. 从前序与中序遍历序列构造二叉树
inline Node<int>* buildTree(std::vector<int>& preorder, std::vector<int>& inorder)
{
    std::unordered_map<int, size_t> map;
    for (int i = 0; i < inorder.size(); i++) {
        map[inorder[i]] = i;
    }
    return build_detail(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, map);
}

// 力扣958. 判断是否是完全二叉树
template<class T>
inline bool is_complete_binary_tree(Node<T>* head)
{
    if (head == nullptr) return true;

    std::queue<Node<T>*> que;
    que.push(head);

    bool is_complete = false;
    while (!que.empty()) {
        Node<T>* cur = que.front();
        que.pop();
        if ((cur->left == nullptr && cur->right != nullptr) ||
            (is_complete && (cur->left != nullptr || cur->right != nullptr))) {
            return false;
        }
        cur->left == nullptr ? (void)0 : que.push(cur->left);
        cur->right == nullptr ? (void)0 : que.push(cur->right);
        if (cur->left == nullptr || cur->right == nullptr) {
            is_complete = true;
        }
    }
    return true;
}

// 力扣222.求完全二叉树的节点个数，时间 < O(n)
template<class T>
inline int countNodes(Node<T>* root)
{
    if (root == nullptr) return 0;
    return f(root, 1, most_left(root, 1));
}

// 力扣236. 普通二叉树上寻找p和q两个节点最近公共祖先
template<class T>
inline Node<T>* lowestCommonAncestor(Node<T>* head, Node<T>* p, Node<T>* q)
{
    if (head == nullptr || head == p || head == q) return head;

    Node<T>* l = lowestCommonAncestor(head->left, p, q);
    Node<T>* r = lowestCommonAncestor(head->right, p, q);

    if (l != nullptr && r != nullptr) return head;
    if (l == nullptr && r == nullptr) return nullptr;
    return l != nullptr ? l : r;
}

// 力扣236. 在搜索二叉树上寻找p和q两个节点最近公共祖先
template<class T>
inline Node<T>* lowestCommonAncestor2(Node<T>* head, Node<T>* p, Node<T>* q)
{
    Node<T>* cur = head;
    while (cur != p && cur != q) {
        if (std::min(p->_value, q->_value) < cur->_value &&
            cur->_value < std::max(p->_value, q->_value))
            break;
        cur = cur->_value < std::min(p->_value, q->_value) ? cur->right : cur->left;
    }
    return cur;
}

// 113. 路径总和 II
class pathSum_II {
    std::vector<int> path;
    int              target;

public:
    inline std::vector<std::vector<int>> pathSum(Node<int>* root, int targetSum)
    {
        target = targetSum;
        std::vector<std::vector<int>> arr;
        int                           sum = 0;
        f(root, arr, sum);
        return arr;
    }

private:
    inline void f(Node<int>* root, std::vector<std::vector<int>>& vvi, int sum)
    {
        if (root->left == nullptr && root->right == nullptr) {
            if (root->_value + sum == target) {
                path.push_back(root->_value);
                vvi.push_back(path);
                path.pop_back();
            }
        }
        else {
            path.push_back(root->_value);
            if (root->left != nullptr) {
                f(root->left, vvi, sum + root->_value);
            }
            if (root->right != nullptr) {
                f(root->right, vvi, sum + root->_value);
            }
            path.pop_back();
        }
    }
};

// 力扣110.给定一个二叉树，判断它是否是平衡二叉树
template<class T>
inline bool isBalanced(Node<T>* root)
{
    bool balance = true;
    height(root, balance);
    return balance;
}

// 力扣98. 给定一个二叉树，判断它是否是二叉搜索树
template<class T>
inline bool isValidBST1(Node<T>* root)
{
    if (root == nullptr) return true;

    std::stack<Node<T>*> stack;
    Node<T>*             pre = nullptr;
    while (!stack.empty() || root != nullptr) {
        if (root != nullptr) {
            stack.push(root);
            root = root->left;
        }
        else {
            root = stack.top();
            stack.pop();
            if (pre != nullptr && pre->_value >= root->_value) return false;
            pre  = root;
            root = root->right;
        }
    }
    return true;
}

// 递归版(节点上的value不能>=类型最大值，<=类型最小值)
template<class T>
inline bool isValidBST2(Node<T>* root, T& min, T& max)
{
    if (root == nullptr) {
        max = T(1) << (sizeof(T) * 8 - 1);
        min = ~max;
        return true;
    }

    bool lok  = isValidBST2(root->left, min, max);
    T    lmin = min;
    T    lmax = max;
    bool rok  = isValidBST2(root->right, min, max);
    T    rmin = min;
    T    rmax = max;
    min       = std::min(std::min(lmin, rmin), root->_value);
    max       = std::max(std::max(lmax, rmax), root->_value);
    return lok && rok && lmax < root->_value && root->_value < rmin;
}

// 力扣669. 修剪二叉搜索树
template<class T>
inline Node<T>* trimBST(Node<T>* root, T low, T high)
{
    if (root == nullptr) return nullptr;

    if (root->_value < low) return trimBST(root->right, low, high);
    if (root->_value > high) return trimBST(root->left, low, high);

    root->left  = trimBST(root->left, low, high);
    root->right = trimBST(root->right, low, high);
    return root;
}

// 力扣337. 打家劫舍 III
template<class T>
inline T rob(Node<T>* root)
{
    T yes = 0, no = 0;
    rob(root, yes, no);
    return yes > no ? yes : no;
}

}   // namespace lxj
#endif